{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of k-Mirror Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kMirror"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #k 镜像数字的和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个 <strong>k 镜像数字</strong>&nbsp;指的是一个在十进制和 k 进制下从前往后读和从后往前读都一样的&nbsp;<strong>没有前导 0</strong>&nbsp;的&nbsp;<strong>正</strong>&nbsp;整数。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，<code>9</code>&nbsp;是一个 2 镜像数字。<code>9</code>&nbsp;在十进制下为&nbsp;<code>9</code>&nbsp;，二进制下为&nbsp;<code>1001</code>&nbsp;，两者从前往后读和从后往前读都一样。</li>\n",
    "\t<li>相反地，<code>4</code>&nbsp;不是一个 2 镜像数字。<code>4</code>&nbsp;在二进制下为&nbsp;<code>100</code>&nbsp;，从前往后和从后往前读不相同。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你进制&nbsp;<code>k</code>&nbsp;和一个数字&nbsp;<code>n</code>&nbsp;，请你返回 k 镜像数字中 <strong>最小</strong> 的 <code>n</code>&nbsp;个数 <strong>之和</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>示例 1：</b></p>\n",
    "\n",
    "<pre><b>输入：</b>k = 2, n = 5\n",
    "<b>输出：</b>25\n",
    "<strong>解释：\n",
    "</strong>最小的 5 个 2 镜像数字和它们的二进制表示如下：\n",
    "  十进制       二进制\n",
    "    1          1\n",
    "    3          11\n",
    "    5          101\n",
    "    7          111\n",
    "    9          1001\n",
    "它们的和为 1 + 3 + 5 + 7 + 9 = 25 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>k = 3, n = 7\n",
    "<b>输出：</b>499\n",
    "<strong>解释：\n",
    "</strong>7 个最小的 3 镜像数字和它们的三进制表示如下：\n",
    "  十进制       三进制\n",
    "    1          1\n",
    "    2          2\n",
    "    4          11\n",
    "    8          22\n",
    "    121        11111\n",
    "    151        12121\n",
    "    212        21212\n",
    "它们的和为 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>k = 7, n = 17\n",
    "<b>输出：</b>20379000\n",
    "<b>解释：</b>17 个最小的 7 镜像数字分别为：\n",
    "1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= k &lt;= 9</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 30</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-k-mirror-numbers](https://leetcode.cn/problems/sum-of-k-mirror-numbers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-k-mirror-numbers](https://leetcode.cn/problems/sum-of-k-mirror-numbers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n5', '3\\n7', '7\\n17']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, nk: int, n: int) -> int:\n",
    "        res = list()\n",
    "        def check(num):\n",
    "            new = list()\n",
    "            while num:\n",
    "                new.append(num % nk)\n",
    "                num //= nk\n",
    "            if new[0] == 0 and new[-1] == 0:\n",
    "                return False\n",
    "            n = len(new)\n",
    "            for i in range(n // 2):\n",
    "                if new[i] != new[n - 1 - i]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        for j in range(6):\n",
    "            for k in range(10 ** j , 10 ** (j + 1)):\n",
    "                a = k // 10\n",
    "                b = 0\n",
    "                cnt = 0\n",
    "                while a:\n",
    "                    b = b * 10 + a % 10\n",
    "                    a //= 10\n",
    "                    cnt += 1\n",
    "                tmp = k * 10 ** cnt + b\n",
    "                # print(tmp)\n",
    "                if check(tmp):\n",
    "                    res.append(tmp)\n",
    "                    if len(res) == n:\n",
    "                        # print(res)\n",
    "                        return sum(res)\n",
    "                k += 1\n",
    "            \n",
    "            for k in range(10 ** j , 10 ** (j + 1)):\n",
    "                a = k\n",
    "                b = 0\n",
    "                cnt = 0\n",
    "                while a:\n",
    "                    b = b * 10 + a % 10\n",
    "                    a //= 10\n",
    "                    cnt += 1\n",
    "                tmp = k * 10 ** cnt + b\n",
    "                if check(tmp):\n",
    "                    res.append(tmp)\n",
    "                    if len(res) == n:\n",
    "                        # print(res)\n",
    "                        return sum(res)\n",
    "                k += 1\n",
    "\n",
    "            \n",
    "        # # print(res)\n",
    "        # return sum(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def MirrorGenerator(k):\n",
    "    for i in range(1, k):\n",
    "        yield i\n",
    "    start, end = 1, k\n",
    "    while True:\n",
    "        for i in range(start, end):\n",
    "            v = i\n",
    "            temp = i\n",
    "            while temp:\n",
    "                v = v * k + temp % k\n",
    "                temp //= k\n",
    "            yield v\n",
    "        for i in range(start, end):\n",
    "            for j in range(k):\n",
    "                v = i * k + j\n",
    "                temp = i\n",
    "                while temp:\n",
    "                    v = v * k + temp % k\n",
    "                    temp //= k\n",
    "                yield v\n",
    "        start, end = end, end * k\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        genk, gen10 = MirrorGenerator(k), MirrorGenerator(10)\n",
    "        xk, x10 = next(genk), next(gen10)\n",
    "        res = 0\n",
    "        while n:\n",
    "            if xk < x10:\n",
    "                xk = next(genk)\n",
    "            elif x10 < xk:\n",
    "                x10 = next(gen10)\n",
    "            else:\n",
    "                n -= 1\n",
    "                res += xk\n",
    "                xk = next(genk)\n",
    "                x10 = next(gen10)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# D = {\n",
    "#     2:{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 58, 7: 157, 8: 470, 9: 1055, 10: 1772, 11: 9219, 12: 18228, 13: 33579, 14: 65802, 15: 105795, 16: 159030, 17: 212865, 18: 286602, 19: 872187, 20: 2630758, 21: 4565149, 22: 6544940, 23: 9674153, 24: 14745858, 25: 20005383, 26: 25846868},\n",
    "#     3:{0: 0, 1: 1, 2: 3, 3: 7, 4: 15, 5: 136, 6: 287, 7: 499, 8: 741, 9: 1225, 10: 1881, 11: 2638, 12: 31730, 13: 80614, 14: 155261, 15: 230718, 16: 306985, 17: 399914, 18: 493653, 19: 1342501, 20: 2863752, 21: 5849644, 22: 9871848, 23: 14090972, 24: 18342496, 25: 22630320, 26: 28367695, 27: 36243482, 28: 44192979},\n",
    "#     4:{0: 0, 1: 1, 2: 3, 3: 6, 4: 11, 5: 21, 6: 36, 7: 53, 8: 74, 9: 99, 10: 128, 11: 162, 12: 200, 13: 242, 14: 288, 15: 339, 16: 394, 17: 453, 18: 516, 19: 581, 20: 666, 21: 771, 22: 896, 23: 1026, 24: 1176, 25: 1346, 26: 1536, 27: 1731, 28: 1946, 29: 2181, 30: 2436},\n",
    "#     5:{0: 0, 1: 1, 2: 3, 3: 6, 4: 10, 5: 16, 6: 28, 7: 46, 8: 70, 9: 96, 10: 127, 11: 163, 12: 204, 13: 250, 14: 302, 15: 359, 16: 421, 17: 488, 18: 560, 19: 638, 20: 721, 21: 809, 22: 902, 23: 1000, 24: 1104, 25: 1213, 26: 1327, 27: 1446, 28: 1570, 29: 1696, 30: 1852},\n",
    "#     6:{0: 0, 1: 1, 2: 3, 3: 6, 4: 10, 5: 15, 6: 22, 7: 36, 8: 57, 9: 85, 10: 120, 11: 157, 12: 200, 13: 249, 14: 304, 15: 365, 16: 432, 17: 506, 18: 586, 19: 672, 20: 764, 21: 862, 22: 966, 23: 1077, 24: 1194, 25: 1317, 26: 1446, 27: 1581, 28: 1722, 29: 1870, 30: 2024},\n",
    "#     7:{0: 0, 1: 1, 2: 3, 3: 6, 4: 10, 5: 15, 6: 21, 7: 29, 8: 45, 9: 69, 10: 101, 11: 141, 12: 189, 13: 239, 14: 296, 15: 360, 16: 431, 17: 509, 18: 594, 19: 686, 20: 786, 21: 893, 22: 1007, 23: 1128, 24: 1256, 25: 1391, 26: 1533, 27: 1683, 28: 1840, 29: 2004, 30: 2175},\n",
    "#     8:{0: 0, 1: 1, 2: 3, 3: 6, 4: 10, 5: 15, 6: 21, 7: 28, 8: 37, 9: 55, 10: 82, 11: 118, 12: 163, 13: 217, 14: 280, 15: 345, 16: 418, 17: 499, 18: 588, 19: 685, 20: 790, 21: 903, 22: 1024, 23: 1154, 24: 1292, 25: 1438, 26: 1592, 27: 1754, 28: 1924, 29: 2102, 30: 2288},\n",
    "#     9:{0: 0, 1: 1, 2: 3, 3: 6, 4: 10, 5: 15, 6: 21, 7: 28, 8: 36, 9: 46, 10: 66, 11: 96, 12: 136, 13: 186, 14: 246, 15: 316, 16: 396, 17: 478, 18: 569, 19: 669, 20: 778, 21: 896, 22: 1023, 23: 1159, 24: 1304, 25: 1458, 26: 1622, 27: 1795, 28: 1977, 29: 2168, 30: 2368}\n",
    "# }\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        # return D[k][n]\n",
    "        def findnxt(x):\n",
    "            s = str(x);l = len(s)\n",
    "            mid = l//2;rv = l-1-mid\n",
    "            while rv >= 0 and s[mid] == '9':\n",
    "                mid += 1\n",
    "                rv -= 1\n",
    "            if rv == -1:return 10**l+1\n",
    "            if mid != rv:\n",
    "                res = int(s[:rv] + str(int(s[rv])+1) + (mid-rv-1)*'0' + str(int(s[mid])+1) + s[mid+1:])\n",
    "            else:\n",
    "                res = int(s[:rv] + str(int(s[rv])+1) + s[mid+1:])\n",
    "            return res\n",
    "        \n",
    "        def trans(m):\n",
    "            s = ''\n",
    "            while m:\n",
    "                s += str(m%k)\n",
    "                m//=k\n",
    "            return s == s[::-1]\n",
    "        \n",
    "        res = 0;v = 1 \n",
    "        for i in range(n):\n",
    "            while not trans(v):\n",
    "                v = findnxt(v)\n",
    "            res += v\n",
    "            v = findnxt(v)\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 折半搜索\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        def isPalindrome(x: int) -> bool:\n",
    "            digit = list()\n",
    "            while x:\n",
    "                digit.append(x % k)\n",
    "                x //= k\n",
    "            return digit == digit[::-1]\n",
    "\n",
    "        left, cnt, ans = 1, 0, 0\n",
    "        while cnt < n:\n",
    "            right = left * 10\n",
    "            # op = 0 表示枚举奇数长度回文，op = 1 表示枚举偶数长度回文\n",
    "            for op in [0, 1]:\n",
    "                # 枚举 i'\n",
    "                for i in range(left, right):\n",
    "                    if cnt == n:\n",
    "                        break\n",
    "                    \n",
    "                    combined = i\n",
    "                    x = (i // 10 if op == 0 else i)\n",
    "                    while x:\n",
    "                        combined = combined * 10 + x % 10\n",
    "                        x //= 10\n",
    "                    if isPalindrome(combined):\n",
    "                        cnt += 1\n",
    "                        ans += combined\n",
    "            left = right\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        def f(x, k):\n",
    "            s = \"\"\n",
    "            while x:\n",
    "                s += str(x % k)\n",
    "                x //= k\n",
    "            return s == s[::-1]\n",
    "        ans = 0\n",
    "        left = 1\n",
    "        while n:\n",
    "            right = left * 10\n",
    "            for op in range(2):\n",
    "                for i in range(left, right):\n",
    "                    x = i\n",
    "                    y = i // 10 if op % 2 == 0 else i\n",
    "                    while y:\n",
    "                        x = x * 10 + y % 10\n",
    "                        y //= 10\n",
    "                    if f(x, k):\n",
    "                        ans += x\n",
    "                        n -= 1\n",
    "                        if n == 0:\n",
    "                            return ans\n",
    "            left = right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def kstr(x, k):\n",
    "    ret = []\n",
    "\n",
    "    while x != 0:\n",
    "        q, r = divmod(x, k)\n",
    "\n",
    "        ret.append(str(r))\n",
    "        x = q\n",
    "\n",
    "    return ret\n",
    "\n",
    "def check(s):\n",
    "    i = 0\n",
    "    j = len(s) - 1\n",
    "    while i < j:\n",
    "        if s[i] != s[j]:\n",
    "            return False\n",
    "\n",
    "        i += 1\n",
    "        j -= 1\n",
    "\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        ret = []\n",
    "\n",
    "        i = 1\n",
    "\n",
    "        while len(ret) < n:\n",
    "            low = i\n",
    "            hi = i * 10\n",
    "\n",
    "            for j in range(low, hi):\n",
    "                s = str(j)\n",
    "                s = s + s[:-1][::-1]\n",
    "\n",
    "                x = int(s)\n",
    "\n",
    "                xk = kstr(x, k)\n",
    "                if check(xk):\n",
    "                    ret.append(x)\n",
    "\n",
    "                    if len(ret) == n:\n",
    "                        return sum(ret)\n",
    "\n",
    "            for j in range(low, hi):\n",
    "                s = str(j)\n",
    "                s = s + s[::-1]\n",
    "\n",
    "                x = int(s)\n",
    "\n",
    "                xk = kstr(x, k)\n",
    "                if check(xk):\n",
    "                    ret.append(x)\n",
    "\n",
    "                    if len(ret) == n:\n",
    "                        return sum(ret)\n",
    "\n",
    "            i = hi\n",
    "\n",
    "        return sum(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        start = 1\n",
    "        end = 10\n",
    "        ret = 0\n",
    "        \n",
    "        def check(i, limit):\n",
    "            nonlocal ret\n",
    "            s = str(i)\n",
    "            n = len(s)\n",
    "            s += s[:(n - limit)][::-1]\n",
    "            x = int(s)\n",
    "            s = []\n",
    "            t = x\n",
    "            while x:\n",
    "                s.append(x % k)\n",
    "                x //= k\n",
    "            if s == s[::-1]:\n",
    "                ret += t\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        while True:\n",
    "            for j in (1, 0):\n",
    "                i = start\n",
    "                while i < end:\n",
    "                    if check(i, j):\n",
    "                        n -= 1\n",
    "                        if n == 0:\n",
    "                            return ret\n",
    "                    i += 1        \n",
    "            start, end = end, end * 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        now = 1\n",
    "        l = 1\n",
    "        cnt = 0\n",
    "        start = 1\n",
    "        end = 10\n",
    "        ret = 0\n",
    "        \n",
    "        def check(i, limit):\n",
    "            nonlocal ret\n",
    "            s = str(i)\n",
    "            n = len(s)\n",
    "            s += s[:(n - limit)][::-1]\n",
    "            # print(i, s)\n",
    "            x = int(s)\n",
    "            s = []\n",
    "            t = x\n",
    "            while x:\n",
    "                s.append(x % k)\n",
    "                x //= k\n",
    "            if s == s[::-1]:\n",
    "                ret += t\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        while True:\n",
    "            i = start\n",
    "            while i < end:\n",
    "                if check(i, 1):\n",
    "                    cnt += 1\n",
    "                    if cnt == n:\n",
    "                        return ret\n",
    "                i += 1\n",
    "            i = start\n",
    "            while i < end:\n",
    "                if check(i, 0):\n",
    "                    cnt += 1\n",
    "                    if cnt == n:\n",
    "                        return ret\n",
    "                i += 1\n",
    "            start, end = end, end * 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        start = 1\n",
    "        end = 10\n",
    "        ret = 0\n",
    "        \n",
    "        def check(i, limit):\n",
    "            s = str(i)\n",
    "            n = len(s)\n",
    "            s += s[:(n - limit)][::-1]\n",
    "            x = int(s)\n",
    "            s = []\n",
    "            t = x\n",
    "            while x:\n",
    "                s.append(x % k)\n",
    "                x //= k\n",
    "            return t if s == s[::-1] else 0\n",
    "  \n",
    "        while True:\n",
    "            for j in (1, 0):\n",
    "                i = start\n",
    "                while i < end:\n",
    "                    t = check(i, j)\n",
    "                    if t:\n",
    "                        ret += t\n",
    "                        n -= 1\n",
    "                        if n == 0:\n",
    "                            return ret\n",
    "                    i += 1        \n",
    "            start, end = end, end * 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "def emumeratePalindrome(\n",
    "    minLength: int, maxLength: int, reverse=False\n",
    ") -> Generator[str, None, None]:\n",
    "    \"\"\"\n",
    "    遍历长度在 `[minLength, maxLength]` 之间的回文数字字符串.\n",
    "    maxLength <= 12.\n",
    "    \"\"\"\n",
    "    if minLength > maxLength:\n",
    "        return\n",
    "    if reverse:\n",
    "        for length in reversed(range(minLength, maxLength + 1)):\n",
    "            start = 10 ** ((length - 1) >> 1)\n",
    "            end = start * 10 - 1\n",
    "            for half in reversed(range(start, end + 1)):\n",
    "                if length & 1:\n",
    "                    yield f\"{half}{str(half)[:-1][::-1]}\"\n",
    "                else:\n",
    "                    yield f\"{half}{str(half)[::-1]}\"\n",
    "    else:\n",
    "        for length in range(minLength, maxLength + 1):\n",
    "            start = 10 ** ((length - 1) >> 1)\n",
    "            end = start * 10 - 1\n",
    "            for half in range(start, end + 1):\n",
    "                if length & 1:\n",
    "                    yield f\"{half}{str(half)[:-1][::-1]}\"\n",
    "                else:\n",
    "                    yield f\"{half}{str(half)[::-1]}\"\n",
    "\n",
    "\n",
    "\n",
    "def check(num: int, radix: int) -> bool:\n",
    "    \"\"\"判断num在radix进制下是否为回文\"\"\"\n",
    "    assert radix >= 2\n",
    "\n",
    "    digits = []\n",
    "    while num:\n",
    "        div, mod = divmod(num, radix)\n",
    "        digits.append(mod)\n",
    "        num = div\n",
    "    return digits == digits[::-1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        res = []\n",
    "        iter = emumeratePalindrome(1, int(1e20))\n",
    "        while len(res) < n:\n",
    "            palindrome = int(next(iter))\n",
    "            if check(palindrome, k):\n",
    "                res.append(palindrome)\n",
    "        return sum(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_k(x,k):\n",
    "    ans = \"\"\n",
    "    while x:\n",
    "        ans+=str(x%k)\n",
    "        x//=k\n",
    "    return ans\n",
    "def check(x):\n",
    "    x = str(x)\n",
    "    n = len(x)\n",
    "    for i in range(n//2):\n",
    "        if x[i]!=x[n-1-i]:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "def get_next_ten(x):\n",
    "    x = list(str(x))\n",
    "    n = len(x)\n",
    "    for i in range(n//2-1 if n%2==0 else n//2,-1,-1):\n",
    "        if x[i]!='9':\n",
    "            x[i] = str(int(x[i])+1)\n",
    "            if n % 2 == 1 and i == n//2:\n",
    "                x[n-1-i] = x[n-1-i]\n",
    "            else:\n",
    "                x[n-1-i] = str(int(x[n-1-i])+1)\n",
    "            for j in range(i+1,n//2 if n%2==0 else n//2+1):\n",
    "                x[j] = '0'\n",
    "                x[n-1-j] = '0'\n",
    "        \n",
    "\n",
    "            return int(\"\".join(x))\n",
    "    else:\n",
    "        cur = 1\n",
    "        for i in range(n):\n",
    "            cur = cur * 10\n",
    "        return cur + 1\n",
    "# print(get_next_ten(191))\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        # return 1\n",
    "        i = 0\n",
    "        x = 1\n",
    "        s = 0\n",
    "        while i<n:\n",
    "            # print(s,x,check(get_k(x,k)),check(x))\n",
    "            if check(get_k(x,k)) and check(x):\n",
    "                s+=x\n",
    "                i+=1\n",
    "            x = get_next_ten(x)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        ans, cnt, digits = 0, 0, 1\n",
    "        bit = [0]\n",
    "        def add1(l):\n",
    "            idx = len(l) - 1\n",
    "            while 1:\n",
    "                l[idx] += 1\n",
    "                if l[idx] < k:\n",
    "                    break\n",
    "                l[idx] = 0\n",
    "                idx -= 1\n",
    "                if idx < 0:\n",
    "                    return -1\n",
    "        \n",
    "        def check(l, d):\n",
    "            x = 0\n",
    "            for idx in range(0, len(l) - d % 2):\n",
    "                x = x * k + l[idx]\n",
    "            for idx in range(len(l) - 1, -1, -1):\n",
    "                x = x * k + l[idx]\n",
    "            m = \"\"\n",
    "            while x > 0:\n",
    "                m = str(x % 10) + m\n",
    "                x //= 10\n",
    "            return [m == m[::-1], int(m)]\n",
    "\n",
    "        while cnt < n:\n",
    "            r = add1(bit)\n",
    "            if r == -1:\n",
    "                digits += 1\n",
    "                bit = [1] + [0] * ((digits - 1) // 2)\n",
    "            [ck, m] = check(bit, digits)\n",
    "            if ck:\n",
    "                ans += m\n",
    "                cnt += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "arr = [\n",
    "    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "     0, 0],\n",
    "    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "     0, 0],\n",
    "    [0, 1, 4, 9, 16, 25, 58, 157, 470, 1055, 1772, 9219, 18228, 33579, 65802, 105795, 159030, 212865, 286602, 872187,\n",
    "     2630758, 4565149, 6544940, 9674153, 14745858, 20005383, 25846868, 39347399, 759196316, 1669569335, 2609044274, 0,\n",
    "     0, 0, 0, 0, 0, 0, 0, 0],\n",
    "    [0, 1, 3, 7, 15, 136, 287, 499, 741, 1225, 1881, 2638, 31730, 80614, 155261, 230718, 306985, 399914, 493653,\n",
    "     1342501, 2863752, 5849644, 9871848, 14090972, 18342496, 22630320, 28367695, 36243482, 44192979, 71904751,\n",
    "     155059889, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "    [0, 1, 3, 6, 11, 66, 439, 832, 1498, 2285, 3224, 11221, 64456, 119711, 175366, 233041, 739646, 2540727, 4755849,\n",
    "     8582132, 12448815, 17500320, 22726545, 27986070, 33283995, 38898160, 44577925, 98400760, 721411086, 1676067545,\n",
    "     53393239260, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "    [0, 1, 3, 6, 10, 16, 104, 356, 638, 1264, 1940, 3161, 18912, 37793, 10125794, 20526195, 48237967, 78560270,\n",
    "     126193944, 192171900, 1000828708, 1832161846, 2664029984, 3500161622, 4336343260, 6849225412, 9446112364,\n",
    "     12339666346, 19101218022, 31215959143, 43401017264, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "    [0, 1, 3, 6, 10, 15, 22, 77, 188, 329, 520, 863, 1297, 2074, 2942, 4383, 12050, 19827, 41849, 81742, 156389, 325250,\n",
    "     1134058, 2043967, 3911648, 7009551, 11241875, 15507499, 19806423, 24322577, 28888231, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "    [0, 1, 3, 6, 10, 15, 21, 29, 150, 321, 563, 855, 17416, 83072, 2220384, 6822448, 13420404, 20379000, 29849749,\n",
    "     91104965, 321578997, 788407661, 1273902245, 1912731081, 2570225837, 3428700695, 29128200347, 69258903451,\n",
    "     115121130305, 176576075721, 241030621167, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "    [0, 1, 3, 6, 10, 15, 21, 28, 37, 158, 450, 783, 1156, 1570, 2155, 5818, 14596, 27727, 41058, 67520, 94182, 124285,\n",
    "     154588, 362290, 991116, 1651182, 3148123, 5083514, 7054305, 11253219, 66619574, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "    [0, 1, 3, 6, 10, 15, 21, 28, 36, 227, 509, 882, 1346, 1901, 2547, 3203, 10089, 35841, 63313, 105637, 156242, 782868,\n",
    "     2323319, 4036490, 5757761, 7586042, 9463823, 11349704, 13750746, 16185088, 18627530, 0, 0, 0, 0, 0, 0, 0, 0, 0]]\n",
    "\n",
    "class Solution:\n",
    "    # 85 / 97\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        return arr[k][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        def nxt_rev(cur):\n",
    "            s = str(cur)\n",
    "            if len(s) % 2:\n",
    "                l = r = len(s) // 2\n",
    "            else:\n",
    "                r = len(s) // 2\n",
    "                l = r - 1\n",
    "            while l >= 0 and s[l] == '9':\n",
    "                l -= 1\n",
    "                r += 1\n",
    "            if l == -1:\n",
    "                return 10 ** len(s) + 1\n",
    "            elif l == r:\n",
    "                return int(s[:l] + str((int(s[l]) + 1)) + s[r + 1:])\n",
    "            return int(s[:l] + str((int(s[l]) + 1)) + '0' * (r - 1 - l) + str((int(s[r]) + 1)) + s[r + 1:])\n",
    "\n",
    "\n",
    "        # 十进制转换为base进制\n",
    "        def convert_to_base(num, base):\n",
    "            ans = []\n",
    "            while num:\n",
    "                ans.append(str(num % base))\n",
    "                num //= base\n",
    "            return \"\".join(ans[::-1])\n",
    "\n",
    "\n",
    "        def is_rev(s):\n",
    "            l, r = 0, len(s) - 1\n",
    "            while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return True\n",
    "\n",
    "        ans = 1\n",
    "        cur = 1\n",
    "        n -= 1\n",
    "        while n:\n",
    "            cur = nxt_rev(cur)\n",
    "            if is_rev(convert_to_base(cur, k)):\n",
    "                ans += cur\n",
    "                n -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        start = 1 \n",
    "        cnt = 0\n",
    "        def check(num):\n",
    "            new = []\n",
    "            while num:\n",
    "                new.append(num % k)\n",
    "                num //= k \n",
    "            return new == new[::-1]\n",
    "        res = 0\n",
    "        while cnt < n:\n",
    "            for op in (1, 0):\n",
    "                if cnt == n:\n",
    "                    break \n",
    "                for i in range(start, start * 10):\n",
    "                    if cnt == n:\n",
    "                        break\n",
    "                    if op == 1:\n",
    "                        new = i \n",
    "                        half = new // 10 \n",
    "                    else:\n",
    "                        new = i\n",
    "                        half = new \n",
    "                    while half:\n",
    "                        new = new * 10 + half % 10 \n",
    "                        half //= 10 \n",
    "                    if check(new):\n",
    "                        res += new \n",
    "                        cnt += 1 \n",
    "            start *= 10 \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        def nxt_rev(cur):\n",
    "            s = str(cur)\n",
    "            if len(s) % 2:\n",
    "                l = r = len(s) // 2\n",
    "            else:\n",
    "                r = len(s) // 2\n",
    "                l = r - 1\n",
    "            while l >= 0 and s[l] == '9':\n",
    "                l -= 1\n",
    "                r += 1\n",
    "            if l == -1:\n",
    "                return 10 ** len(s) + 1\n",
    "            elif l == r:\n",
    "                return int(s[:l] + str((int(s[l]) + 1)) + s[r + 1:])\n",
    "            return int(s[:l] + str((int(s[l]) + 1)) + '0' * (r - 1 - l) + str((int(s[r]) + 1)) + s[r + 1:])\n",
    "\n",
    "\n",
    "        # 十进制转换为base进制\n",
    "        def is_rev(num):\n",
    "            ans = ''\n",
    "            while num:\n",
    "                ans+=(str(num % k))\n",
    "                num //= k\n",
    "            return ans == ans[::-1]\n",
    "\n",
    "        ans = 1\n",
    "        cur = 1\n",
    "        n -= 1\n",
    "        while n:\n",
    "            cur = nxt_rev(cur)\n",
    "            if is_rev(cur):\n",
    "                ans += cur\n",
    "                n -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理\n",
    "class Solution:\n",
    "\n",
    "    ANS = [\n",
    "            [1, 3, 5, 7, 9, 33, 99, 313, 585, 717, 7447, 9009, 15351, 32223, 39993, 53235, 53835, 73737, 585585, 1758571, 1934391, 1979791, 3129213, 5071705, 5259525, 5841485, 13500531, 719848917, 910373019, 939474939],\n",
    "            [1, 2, 4, 8, 121, 151, 212, 242, 484, 656, 757, 29092, 48884, 74647, 75457, 76267, 92929, 93739, 848848, 1521251, 2985892, 4022204, 4219124, 4251524, 4287824, 5737375, 7875787, 7949497, 27711772, 83155138],\n",
    "            [1, 2, 3, 5, 55, 373, 393, 666, 787, 939, 7997, 53235, 55255, 55655, 57675, 506605, 1801081, 2215122, 3826283, 3866683, 5051505, 5226225, 5259525, 5297925, 5614165, 5679765, 53822835, 623010326, 954656459, 51717171715],\n",
    "            [1, 2, 3, 4, 6, 88, 252, 282, 626, 676, 1221, 15751, 18881, 10088001, 10400401, 27711772, 30322303, 47633674, 65977956, 808656808, 831333138, 831868138, 836131638, 836181638, 2512882152, 2596886952, 2893553982, 6761551676, 12114741121, 12185058121],\n",
    "            [1, 2, 3, 4, 5, 7, 55, 111, 141, 191, 343, 434, 777, 868, 1441, 7667, 7777, 22022, 39893, 74647, 168861, 808808, 909909, 1867681, 3097903, 4232324, 4265624, 4298924, 4516154, 4565654],\n",
    "            [1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596, 9470749, 61255216, 230474032, 466828664, 485494584, 638828836, 657494756, 858474858, 25699499652, 40130703104, 45862226854, 61454945416, 64454545446],\n",
    "            [1, 2, 3, 4, 5, 6, 7, 9, 121, 292, 333, 373, 414, 585, 3663, 8778, 13131, 13331, 26462, 26662, 30103, 30303, 207702, 628826, 660066, 1496941, 1935391, 1970791, 4198914, 55366355],\n",
    "            [1, 2, 3, 4, 5, 6, 7, 8, 191, 282, 373, 464, 555, 646, 656, 6886, 25752, 27472, 42324, 50605, 626626, 1540451, 1713171, 1721271, 1828281, 1877781, 1885881, 2401042, 2434342, 2442442],\n",
    "        ]\n",
    "\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        return sum(Solution.ANS[k - 2][:n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        D = {\n",
    "    2:{1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 58, 7: 157, 8: 470, 9: 1055, 10: 1772, 11: 9219, 12: 18228, 13: 33579, 14: 65802, 15: 105795, 16: 159030, 17: 212865, 18: 286602, 19: 872187, 20: 2630758, 21: 4565149, 22: 6544940, 23: 9674153, 24: 14745858, 25: 20005383, 26: 25846868, 27: 39347399, 28: 759196316, 29: 1669569335, 30: 2609044274},\n",
    "    3:{1: 1, 2: 3, 3: 7, 4: 15, 5: 136, 6: 287, 7: 499, 8: 741, 9: 1225, 10: 1881, 11: 2638, 12: 31730, 13: 80614, 14: 155261, 15: 230718, 16: 306985, 17: 399914, 18: 493653, 19: 1342501, 20: 2863752, 21: 5849644, 22: 9871848, 23: 14090972, 24: 18342496, 25: 22630320, 26: 28367695, 27: 36243482, 28: 44192979, 29: 71904751, 30: 155059889},\n",
    "    4:{1: 1, 2: 3, 3: 6, 4: 11, 5: 66, 6: 439, 7: 832, 8: 1498, 9: 2285, 10: 3224, 11: 11221, 12: 64456, 13: 119711, 14: 175366, 15: 233041, 16: 739646, 17: 2540727, 18: 4755849, 19: 8582132, 20: 12448815, 21: 17500320, 22: 22726545, 23: 27986070, 24: 33283995, 25: 38898160, 26: 44577925, 27: 98400760, 28: 721411086, 29: 1676067545, 30: 53393239260},\n",
    "    5:{1: 1, 2: 3, 3: 6, 4: 10, 5: 16, 6: 104, 7: 356, 8: 638, 9: 1264, 10: 1940, 11: 3161, 12: 18912, 13: 37793, 14: 10125794, 15: 20526195, 16: 48237967, 17: 78560270, 18: 126193944, 19: 192171900, 20: 1000828708, 21: 1832161846, 22: 2664029984, 23: 3500161622, 24: 4336343260, 25: 6849225412, 26: 9446112364, 27: 12339666346, 28: 19101218022, 29: 31215959143, 30: 43401017264},\n",
    "    6:{1: 1, 2: 3, 3: 6, 4: 10, 5: 15, 6: 22, 7: 77, 8: 188, 9: 329, 10: 520, 11: 863, 12: 1297, 13: 2074, 14: 2942, 15: 4383, 16: 12050, 17: 19827, 18: 41849, 19: 81742, 20: 156389, 21: 325250, 22: 1134058, 23: 2043967, 24: 3911648, 25: 7009551, 26: 11241875, 27: 15507499, 28: 19806423, 29: 24322577, 30: 28888231},\n",
    "    7:{1: 1, 2: 3, 3: 6, 4: 10, 5: 15, 6: 21, 7: 29, 8: 150, 9: 321, 10: 563, 11: 855, 12: 17416, 13: 83072, 14: 2220384, 15: 6822448, 16: 13420404, 17: 20379000, 18: 29849749, 19: 91104965, 20: 321578997, 21: 788407661, 22: 1273902245, 23: 1912731081, 24: 2570225837, 25: 3428700695, 26: 29128200347, 27: 69258903451, 28: 115121130305, 29: 176576075721, 30: 241030621167},\n",
    "    8:{1: 1, 2: 3, 3: 6, 4: 10, 5: 15, 6: 21, 7: 28, 8: 37, 9: 158, 10: 450, 11: 783, 12: 1156, 13: 1570, 14: 2155, 15: 5818, 16: 14596, 17: 27727, 18: 41058, 19: 67520, 20: 94182, 21: 124285, 22: 154588, 23: 362290, 24: 991116, 25: 1651182, 26: 3148123, 27: 5083514, 28: 7054305, 29: 11253219, 30: 66619574},\n",
    "    9:{1: 1, 2: 3, 3: 6, 4: 10, 5: 15, 6: 21, 7: 28, 8: 36, 9: 227, 10: 509, 11: 882, 12: 1346, 13: 1901, 14: 2547, 15: 3203, 16: 10089, 17: 35841, 18: 63313, 19: 105637, 20: 156242, 21: 782868, 22: 2323319, 23: 4036490, 24: 5757761, 25: 7586042, 26: 9463823, 27: 11349704, 28: 13750746, 29: 16185088, 30: 18627530}\n",
    "}\n",
    "        return D[k][n]\n",
    "        def findnxt(x):\n",
    "            s = str(x);l = len(s)\n",
    "            if Counter(s)['9'] == l:\n",
    "                return int('1'+(l-1)*'0'+'1')\n",
    "            mid = l//2;rv = l-1-mid\n",
    "            while rv >= 0 and s[mid] == '9':\n",
    "                mid += 1\n",
    "                rv -= 1\n",
    "            if mid != rv:\n",
    "                res = int(s[:rv] + str(int(s[rv])+1) + (mid-rv-1)*'0' + str(int(s[mid])+1) + s[mid+1:])\n",
    "            else:\n",
    "                res = int(s[:rv] + str(int(s[rv])+1) + s[mid+1:])\n",
    "            return res\n",
    "        \n",
    "        def trans(m):\n",
    "            s = ''\n",
    "            while m:\n",
    "                s += str(m%k)\n",
    "                m//=k\n",
    "            return s == s[::-1]\n",
    "        D = {}\n",
    "        res = 0;v = 1 \n",
    "        for i in range(1,31):\n",
    "            while not trans(v):\n",
    "                v = findnxt(v)\n",
    "            \n",
    "            res += v\n",
    "            D[i] = res\n",
    "            v = findnxt(v)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 一把把所有结果算出来，剩下就是O（1）\n",
    "def int2k(n, k):\n",
    "    res = ''\n",
    "    n1 = n\n",
    "    while n:\n",
    "        s = n // k\n",
    "        r = n % k\n",
    "        n = s\n",
    "        res = str(r) + res\n",
    "    return res\n",
    "\n",
    "cnt = [[] for _ in range(10)]\n",
    "nums = [i for i in range(1, 10)]\n",
    "for v in range(1, 10**5):\n",
    "    nums.append(int(str(v) + str(v)[::-1]))\n",
    "    for k in range(10):\n",
    "        nums.append(int(str(v) + str(k) + str(v)[::-1]))\n",
    "\n",
    "nums.sort()\n",
    "for i in range(2, 10):\n",
    "    for v in nums:\n",
    "        s = int2k(v, i)\n",
    "        if s == s[::-1]:\n",
    "            cnt[i].append(v)\n",
    "        if len(cnt[i]) >= 30:\n",
    "            break\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        # 1 <= n <= 30 ;; 示例已经说明暴力是解决不了问题的\n",
    "        return sum(cnt[k][:n])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "def int_base_r(num, base):\n",
    "    if num == 0: return '0'\n",
    "    res = []\n",
    "    while num:\n",
    "        res.append(str(num % base))\n",
    "        num //= base\n",
    "    return res\n",
    "\n",
    "\n",
    "def calc(num0, num1):\n",
    "    ret = num0\n",
    "    while num1:\n",
    "        num1, r = divmod(num1, 10)\n",
    "        ret = ret * 10 + r\n",
    "    return ret\n",
    "\n",
    "\n",
    "# 下一个回文数组，获取的是[10^(num_len-1), 10^num_len)范围内的回文\n",
    "# 相同范围内，奇数组的数据一定小于偶数组的，所以先计算奇数组再计算偶数组\n",
    "def next_palindrome_group(num_len: int, e):\n",
    "    ret = []\n",
    "    for num in range(10**(num_len - 1), 10**num_len):\n",
    "        if e == 0:  # odd\n",
    "            ret.append(calc(num, num // 10))\n",
    "        else:  # even\n",
    "            ret.append(calc(num, num))\n",
    "    return ret\n",
    "\n",
    "\n",
    "arr = [[0] for _ in range(10)]\n",
    "\n",
    "\n",
    "def build_arr():\n",
    "    size, e = 1, 0\n",
    "    k_set = set(range(2, 10))\n",
    "    while True:\n",
    "        nums = next_palindrome_group(size, e)\n",
    "        for num in nums:\n",
    "            n_k_set = set()\n",
    "            for k in k_set:\n",
    "                if len(arr[k]) == 31:\n",
    "                    continue\n",
    "                n_k_set.add(k)\n",
    "                bs = int_base_r(num, k)\n",
    "                if bs == bs[::-1]:\n",
    "                    arr[k].append(num + arr[k][-1])\n",
    "            k_set = n_k_set\n",
    "            if not k_set: return\n",
    "        size += e\n",
    "        e ^= 1\n",
    "\n",
    "\n",
    "build_arr()\n",
    "\n",
    "# 打表\n",
    "# arr = [[0], [0],\n",
    "#        [\n",
    "#            0, 1, 4, 9, 16, 25, 58, 157, 470, 1055, 1772, 9219, 18228, 33579, 65802, 105795, 159030, 212865, 286602, 872187, 2630758, 4565149, 6544940, 9674153, 14745858, 20005383, 25846868, 39347399,\n",
    "#            759196316, 1669569335, 2609044274\n",
    "#        ],\n",
    "#        [\n",
    "#            0, 1, 3, 7, 15, 136, 287, 499, 741, 1225, 1881, 2638, 31730, 80614, 155261, 230718, 306985, 399914, 493653, 1342501, 2863752, 5849644, 9871848, 14090972, 18342496, 22630320, 28367695,\n",
    "#            36243482, 44192979, 71904751, 155059889\n",
    "#        ],\n",
    "#        [\n",
    "#            0, 1, 3, 6, 11, 66, 439, 832, 1498, 2285, 3224, 11221, 64456, 119711, 175366, 233041, 739646, 2540727, 4755849, 8582132, 12448815, 17500320, 22726545, 27986070, 33283995, 38898160,\n",
    "#            44577925, 98400760, 721411086, 1676067545, 53393239260\n",
    "#        ],\n",
    "#        [\n",
    "#            0, 1, 3, 6, 10, 16, 104, 356, 638, 1264, 1940, 3161, 18912, 37793, 10125794, 20526195, 48237967, 78560270, 126193944, 192171900, 1000828708, 1832161846, 2664029984, 3500161622, 4336343260,\n",
    "#            6849225412, 9446112364, 12339666346, 19101218022, 31215959143, 43401017264\n",
    "#        ],\n",
    "#        [\n",
    "#            0, 1, 3, 6, 10, 15, 22, 77, 188, 329, 520, 863, 1297, 2074, 2942, 4383, 12050, 19827, 41849, 81742, 156389, 325250, 1134058, 2043967, 3911648, 7009551, 11241875, 15507499, 19806423,\n",
    "#            24322577, 28888231\n",
    "#        ],\n",
    "#        [\n",
    "#            0, 1, 3, 6, 10, 15, 21, 29, 150, 321, 563, 855, 17416, 83072, 2220384, 6822448, 13420404, 20379000, 29849749, 91104965, 321578997, 788407661, 1273902245, 1912731081, 2570225837, 3428700695,\n",
    "#            29128200347, 69258903451, 115121130305, 176576075721, 241030621167\n",
    "#        ],\n",
    "#        [\n",
    "#            0, 1, 3, 6, 10, 15, 21, 28, 37, 158, 450, 783, 1156, 1570, 2155, 5818, 14596, 27727, 41058, 67520, 94182, 124285, 154588, 362290, 991116, 1651182, 3148123, 5083514, 7054305, 11253219,\n",
    "#            66619574\n",
    "#        ],\n",
    "#        [\n",
    "#            0, 1, 3, 6, 10, 15, 21, 28, 36, 227, 509, 882, 1346, 1901, 2547, 3203, 10089, 35841, 63313, 105637, 156242, 782868, 2323319, 4036490, 5757761, 7586042, 9463823, 11349704, 13750746,\n",
    "#            16185088, 18627530\n",
    "#        ]]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        return arr[k][n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_k_bin_of_n(n, k):\n",
    "    # 整数n的k进制计算（支持正数进制与负数进制）二进制、三进制、十六进制、负进制\n",
    "    if n == 0:\n",
    "        return [0]\n",
    "    if k == 0:\n",
    "        return []\n",
    "    # 支持正负数\n",
    "    pos = 1 if k > 0 else -1\n",
    "    k = abs(k)\n",
    "    lst = []\n",
    "    while n:\n",
    "        lst.append(n % k)\n",
    "        n //= k\n",
    "        n *= pos\n",
    "    lst.reverse()\n",
    "    # 最高支持三十六进制的表达\n",
    "    # \"0123456789\" + \"\".join(chr(i+ord(\"A\")) for i in range(26))\n",
    "    return lst\n",
    "\n",
    "\n",
    "class PalindromeNum:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def get_palindrome_num_1(n):\n",
    "        # 使用动态规划模拟对称的回文子串添加\n",
    "        dp = [[\"\"], [str(i) for i in range(10)]]\n",
    "        for k in range(2, n+1):\n",
    "            if k % 2 == 1:\n",
    "                m = k // 2\n",
    "                lst = []\n",
    "                for st in dp[-1]:\n",
    "                    for i in range(10):\n",
    "                        lst.append(st[:m] + str(i) + st[m:])\n",
    "                dp.append(lst)\n",
    "            else:\n",
    "                lst = []\n",
    "                for st in dp[-2]:\n",
    "                    for i in range(10):\n",
    "                        lst.append(str(i) + st + str(i))\n",
    "                dp.append(lst)\n",
    "\n",
    "        # 取出所有的回文数字并排序\n",
    "        nums = []\n",
    "        for lst in dp:\n",
    "            for num in lst:\n",
    "                if num and num[0] != \"0\":\n",
    "                    nums.append(int(num))\n",
    "        nums.sort()\n",
    "        # 计算出长度小于等于 n 的所有正回文数\n",
    "        return nums\n",
    "\n",
    "    @staticmethod\n",
    "    def get_palindrome_num_2(n):\n",
    "        assert n >= 1\n",
    "        # 计算出长度小于等于 n 的所有正回文数\n",
    "        nums = list(range(1, 10))\n",
    "        x = 1\n",
    "        while len(str(x))*2 <= n:\n",
    "            num = str(x) + str(x)[::-1]\n",
    "            nums.append(int(num))\n",
    "            if len(str(x))*2 + 1 <= n:\n",
    "                for d in range(10):\n",
    "                    nums.append(int(str(x) + str(d) + str(x)[::-1]))\n",
    "            x += 1\n",
    "        nums.sort()\n",
    "        return nums\n",
    "\n",
    "\n",
    "dct = defaultdict(list)\n",
    "nums = PalindromeNum().get_palindrome_num_2(12)\n",
    "for k in range(2, 10):\n",
    "    for num in nums:\n",
    "        lst = get_k_bin_of_n(num, k)\n",
    "        if lst == lst[::-1]:\n",
    "            dct[k].append(num)\n",
    "            if len(dct[k]) >= 30:\n",
    "                break\n",
    "\n",
    "# for num in PalindromeNum().get_result(12):\n",
    "#     for k in range(2, 10):\n",
    "#         lst = get_k_bin_of_n(num, k)\n",
    "#         if lst == lst[::-1]:\n",
    "#             dct[k].append(num)\n",
    "\n",
    "for k in range(2, 10):\n",
    "    assert len(dct[k]) >= 30\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        return sum(dct[k][:n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        if n < k:\n",
    "            return (n + 1) * n // 2\n",
    "        lst = list(range(1, k))\n",
    "        length = 1\n",
    "        temp = []\n",
    "        num_lst = []\n",
    "\n",
    "        def dfs(mid):\n",
    "            if len(temp) == length:\n",
    "                s = ''.join(temp)\n",
    "                if mid == 1:\n",
    "                    num_lst.append(s + s[::-1])\n",
    "                else:\n",
    "                    for i in range(mid):\n",
    "                        num_lst.append(s + str(i) + s[::-1])\n",
    "                return\n",
    "            for i in range(k):\n",
    "                if not temp and not i:\n",
    "                    continue\n",
    "                temp.append(str(i))\n",
    "                dfs(mid)\n",
    "                temp.pop()\n",
    "\n",
    "        while len(lst) < n:\n",
    "            num_lst = []\n",
    "            dfs(1)\n",
    "            for num in num_lst:\n",
    "                num_s = str(int(num, base=k))\n",
    "                if num_s == num_s[::-1]:\n",
    "                    lst.append(int(num_s))\n",
    "                    if len(lst) == n:\n",
    "                        break\n",
    "            if len(lst) == n:\n",
    "                break\n",
    "            num_lst = []\n",
    "            dfs(k)\n",
    "            for num in num_lst:\n",
    "                num_s = str(int(num, base=k))\n",
    "                if num_s == num_s[::-1]:\n",
    "                    lst.append(int(num_s))\n",
    "                    if len(lst) == n:\n",
    "                        break\n",
    "            length += 1\n",
    "        return sum(lst)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kMirror(self, k: int, n: int) -> int:\n",
    "        targetLis = []\n",
    "        def check(i):\n",
    "            lis = []\n",
    "            while i:\n",
    "                lis.append(i % k)\n",
    "                i //= k\n",
    "            return lis == lis[::-1]\n",
    "        \n",
    "        numStr = '0123456789'\n",
    "        q = list(numStr[1:])\n",
    "        while q:\n",
    "            nxt = []\n",
    "            for s in q:\n",
    "                i = int(s)\n",
    "                if check(i):\n",
    "                    targetLis.append(i)\n",
    "                    if len(targetLis) == n: return sum(targetLis)\n",
    "                L = len(s)\n",
    "                midx = L // 2\n",
    "                if L & 1:\n",
    "                    nxt.append(s[:midx] + s[midx] + s[midx:])\n",
    "                else:\n",
    "                    for ns in numStr:\n",
    "                        nxt.append(s[:midx] + ns + s[midx:])\n",
    "            \n",
    "            q = nxt"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
